#include "MyIncludes.h"
#include "Node.h"
void Node::init()
{
	left = NULL;
	min2 =  StringKey(EMPTY_KEY);
	middle = NULL;
	min3= StringKey(EMPTY_KEY);
	right = NULL;
	parent = NULL;
}


Node::Node()
{
	init();
}

Node::Node(Worker* value, StringKey key)
{
	init();
	valueKey = key;
	this->value = value;

	min2 = key;
	absoluteMin = key;
}

Node* Node::FindDelete(StringKey key, Worker* &worker)
{
	if(this->IsLeaf())
	{
		if(key.Compare(this->valueKey) == 0)
		{
			worker = this->value;
			return this;
		}
		else
		{
			return NULL;
		}
	}
	else
	{
		Node* nodeFound = NULL;
		if(left != NULL && key.Compare(min2) <= 0)
		{
			nodeFound = left->FindDelete(key, worker);
		}
		if(middle != NULL && nodeFound == NULL && (min3.isEmpty() || key.Compare(min3) <= 0))
		{
			nodeFound = middle->FindDelete(key, worker);
		}
		if(right != NULL && nodeFound == NULL)
		{
			nodeFound = right->FindDelete(key, worker);
		}

		// return from recursion
		Node* notToDelete = nodeFound;

		if(notToDelete != NULL)
		{
			if(NonRecursiveDelete(notToDelete) == false) 
			{
				// less than 2 mode in current node
				if(parent == NULL)
				{
					//currently in root
					FixOrder();
					return this->getRemaningNode();
				}
				Node* brother = parent->getBrother(this);
				if(brother->numOfNodes() == 3)
				{
					// borrow from brother
					Node* node = brother->borrow(this);
					NoneRecursiveInsert(node);
					//FixOrder();
				}
				else
				{
					brother->NoneRecursiveInsert(getRemaningNode());
					//todo insert node here
				}
				FixOrder();
				return this; // delete myself
			}
			else
			{
				//nothing more to delete
				FixOrder();
				return NULL; // stop deleting
			}
		}
		else
		{
			FixOrder();
			return NULL;
		}

	}
}

void Node::printByOrder( ofstream & file)
{
	if(IsLeaf())
	{
		Worker* worker = this->value;
		file << worker->getKey()->getValue() << "\t" << worker->getRank() << "\t" << worker->getSeniority() << "\n";
	}
	else
	{
		if(this->left != NULL)
		{
			this->left->printByOrder(file);
		}
		if(this->middle != NULL)
		{
			this->middle->printByOrder(file);
		}
		if(this->right != NULL)
		{
			this->right->printByOrder(file);
		}
	}
}

Node* Node::borrow(Node* node)
{
	Node* nodeToBorrow;
	if(node->absoluteMin.Compare(min2) <= 0)
	{
		nodeToBorrow = left;
		left = NULL;
	}
	else if(node->absoluteMin.Compare(min2) > 0 && (min3.isEmpty() || node->absoluteMin.Compare(min3) <= 0))
	{
		nodeToBorrow = middle;
		middle = NULL;
	}
	else if(!(min3.isEmpty()) && node->absoluteMin.Compare(min3) >= 0)
	{
		nodeToBorrow = right;
	}
	FixOrder();
	return nodeToBorrow;
}
Node* Node::getRemaningNode()
{
	if(left != NULL)
	{
		return left;
	}
	else if (middle != NULL)
	{
		return middle;
	}
	else if(right != NULL)
	{
		return right;
	}
}

void Node::FreeAllElements()
{
	if(IsLeaf())
	{
		delete this->value;
		return;
	}
	if(left != NULL)
	{
		left->FreeAllElements();
		delete left;
		left = NULL;
	}
	if(middle != NULL)
	{
		middle->FreeAllElements();
		delete middle;
		middle = NULL;
	}
	if(right != NULL)
	{
		right->FreeAllElements();
		delete right;
		right = NULL;
	}
}
Node* Node::getBrother(Node* sonToSkip)
{
	Node* brother;
	if(left == sonToSkip)
	{
		brother = middle;
	}
	else if(middle == sonToSkip)
	{
		// choose brother - if the left or the right one
		if(min2.isEmpty() || sonToSkip->absoluteMin.Compare(min2) <= 0 )
		{
			brother = left;
		}
		else
		{
			brother = right;
		}
	}
	else if(right == sonToSkip)
	{
		brother = middle;
	}
	return brother;

}

Node* Node::Delete(StringKey key, Worker* &worker) 
{
	Node* newNode = FindDelete(key, worker);
	if(newNode != NULL)
	{
		delete newNode->parent;
		newNode->parent = NULL;
		return newNode;
	}
	else
	{
		return this;
	}
}

int Node::numOfNodes()
{
	int sum = 0;
	if(left != NULL)
	{
		sum++;
	}
	if(middle != NULL)
	{
		sum ++;
	}
	if(right != NULL)
	{
		sum++;
	}
	return sum;

}

bool Node::NonRecursiveDelete(Node* node)
{
	Node* nodeToDelete = NULL;
	if(left != NULL && left->absoluteMin.Compare(node->absoluteMin) == 0)
	{
		delete left;
		left = NULL;
	}
	else if(middle!= NULL && middle->absoluteMin.Compare(node->absoluteMin) == 0)
	{
		delete middle;
		middle = NULL;
	}
	else if(right != NULL && right->absoluteMin.Compare(node->absoluteMin) == 0)
	{
		delete right;
		right = NULL;
	}
	
	if (numOfNodes() < 2)
	{
		return false;
	}
	else
	{
		FixOrder();
		return true;
	}
}

// create a  new node -- a leaf
// find the
// father to insert to 
// inserts -splits all the way to the root
// return NULL if inserted
// if root changed return Node* root
Node* Node::Insert(Node* node)
{
	Node* father = this->FindFather(node->valueKey);
	Node* root = father->SplitInsert(node);

	if (root != NULL)
	{
		return root;
	}
	else
	{
		return this;
	}
}

bool Node::NoneRecursiveInsert(Node* node)
{
	if(left == NULL)
	{
		// should get here only in init of the root node
		left = node;
		left->parent = this;
	}
	else if(middle == NULL)
	{
		middle = node;
		middle->parent = this;
	}
	else if(right == NULL)
	{
		right = node;
		right->parent = this;
	}
	else
	{
//		node->parent = this;
		return false;
	}
	node->parent = this;

	FixOrder();
	return true;
}

void Node::updateMinimums()
{
	if(middle!= NULL)
	{
		min2 = middle->absoluteMin;
	}
	else
	{
		min2 = StringKey(EMPTY_KEY);
	}

	if(right != NULL)
	{
		min3 = right-> absoluteMin;
	}
	else
	{
		min3 = StringKey(EMPTY_KEY);
	}

	StringKey smallestMin = left->absoluteMin;
	if(middle != NULL && middle->absoluteMin.Compare(smallestMin) <= 0 )
	{
		smallestMin = middle->absoluteMin;
	}
	if(right != NULL && right->absoluteMin.Compare(smallestMin) <= 0 )
	{
		smallestMin = right->absoluteMin;
	}
	absoluteMin = smallestMin;
}

// returns NULL inserted
// returns root Node* is root has changed;
Node* Node::SplitInsert(Node* son)
{
	if(NoneRecursiveInsert(son) == true)
	{
		this->FixOrder();
		if(this->parent == NULL)
		{
			// added to root - root has changed
			return this;
		}
		else
		{
			//root hasn't changed
			return NULL;
		}
	}
	Node* brother = new Node();
	if(son->absoluteMin.Compare(min2) <= 0)
	{
		// add to left
		brother->left = son;
		brother->middle = this->left;

		this->left = this->middle;
		this->middle = this->right;
	}
	else if(son->absoluteMin.Compare(min2) >= 0 && son->absoluteMin.Compare(min3) <=0)
	{
		// add to middle
		Node* add_to_brother;
		Node* add_to_this;
		if(son->absoluteMin.Compare(middle->absoluteMin) <= 0)
		{
			add_to_brother = son;
			add_to_this = middle;
		}
		else
		{
			add_to_brother = middle;
			add_to_this = son;
		}

		brother->left = this->left;
		brother->middle = add_to_brother;
		add_to_brother->parent = brother;
		

		this->left = add_to_this;
		this->middle = this->right;
		right->parent = this;
		add_to_this->parent = middle;
		
	}
	else
	{
		// add to right
		if(this->right->absoluteMin.Compare(son->absoluteMin) <= 0)
		{
			brother->left = this->right;
			brother->middle = son;
			son->parent = brother;
			right->parent = brother;
		}
		else
		{
			brother->left = son;
			brother->middle = this->right;
			right->parent = brother;
			son -> parent = brother;
		}
	}

	this->right = NULL;

	if(parent == NULL)
	{
		// got to root
		Node* root = new Node();
		if(brother->absoluteMin.Compare(this->absoluteMin) <= 0)
		{
			root->left = brother;
			root->middle = this;
			middle -> parent = root;
			brother -> parent  = root;
		}
		else
		{
			root->left = this;
			root->middle = brother;
			middle -> parent = root;
			brother -> parent  = root;
		}
		parent = root;

		
		this->FixOrder();
		brother->FixOrder();
		son->FixOrder();
		parent->FixOrder();
		return root;
	}
	else
	{		
		this->FixOrder();
		brother->FixOrder();
		son->FixOrder();
		parent->FixOrder();
		return parent->SplitInsert(brother);
	}
	
	
	
}

void Node::FixOrder()
{
	if(this->IsLeaf())
	{
		return;
	}
	if(middle == NULL && right != NULL)
	{
		middle = right;
		right = NULL;
	}
	if(middle != NULL && right != NULL)
	{
		if(middle->absoluteMin.Compare(right->absoluteMin) >= 0)
		{
			Node* temp =right;
			right = middle;
			middle = temp;

		}
	}
	if(left == NULL && middle != NULL)
	{
		left = middle;
		middle = right;
		right = NULL;
	}
	if(left != NULL && middle != NULL)
	{
		if(left->absoluteMin.Compare(middle->absoluteMin) >= 0)
		{
			Node* temp = middle;
			middle = left;
			left = temp;
		}
	}
	if(middle != NULL && right != NULL)
	{
		if(middle->absoluteMin.Compare(right->absoluteMin) >= 0)
		{
			Node* temp =right;
			right = middle;
			middle = temp;
		}
	}

	// fix sons paernts link
	if(left != NULL)
	{
		left->parent = this;
	}
	if(middle!= NULL)
	{
		middle->parent = this;
	}
	if(right != NULL)
	{
		right->parent = this;
	}
	updateMinimums();
}
Node* Node::FindFather(StringKey key)
{
	Node* current = this;
	bool foundFather = false;

	while(!foundFather)
	{
		if ((current->left != NULL && current->left->IsLeaf()) ||
			(current->middle != NULL && current->middle->IsLeaf()) ||
			(current->right != NULL && current->right->IsLeaf()))
		{
			// got to father
			foundFather = true;
		}
		else if (current->left == NULL && current->middle == NULL)
		{
			// only happens in root
			foundFather = true;
		}

		else if(key.Compare(current->left->min2) <= 0)
		{
			if(current->left == NULL)
			{
				foundFather = true;
			}
			else
			{
				current = current->left;
			}
		}
		else if(current->min3.Compare(StringKey(EMPTY_KEY)) == 0)
		{			
			if(current->middle == NULL)
			{
				foundFather = true;
			}
			else
			{
				current = current->middle;
			}
		}
		else if(key.Compare(current->left->min3) <= 0)
		{
			if(current->middle == NULL)
			{
				foundFather = true;
			}
			else
			{
				current = current->middle;
			}
		}
		else
		{
			if(current->right == NULL)
			{
				foundFather = true;
			}
			else
			{
				current = current->right;
			}
		}
	}

	if(this == current)
	{
		// happends only with the root Node;
		return current;
	}

	return current;
}

Node* Node::Find(StringKey key)
{
	if(this->IsLeaf())
	{
		if(key.Compare(this->valueKey) == 0)
		{
			return this;
		}
		else
		{
			return NULL;
		}
	}
	else
	{
		Node* nodeFound = NULL;
		if(left != NULL && (min2.isEmpty() || key.Compare(min2) <= 0))
		{
			nodeFound = left->Find(key);
		}
		if(middle != NULL && nodeFound == NULL && (min3.isEmpty() || key.Compare(min3) <= 0))
		{
			nodeFound = middle->Find(key);
		}
		if(right != NULL && nodeFound == NULL)
		{
			nodeFound = right->Find(key);
		}
		return nodeFound;

	}
}

bool Node::IsLeaf()
{
	if(left == NULL && middle == NULL && right == NULL)
	{
		return true;
	}
	else
	{
		return false;
	}
}

StringKey Node::GetMin()
{
	return absoluteMin;
}

void Node::printNode(int level, char side)
{
	if(this->IsLeaf())
	{
		for(int i=0; i<= level; i++)
		{
			cout << "\t";
		}
		cout << side << ":"<< "key:" << valueKey.value << " value:" << /*value <<*/ endl;
		return;
	}
	else
	{
		for(int i=0; i< level; i++)
		{
			cout << "\t";
		}
		cout << side << ":" << "(" << min2.value;
		cout << "," ;
		cout << min3.value << ")" ;
		cout << " abs min:" << absoluteMin.value << endl;
		if(left != NULL)
		{
			left->printNode(level+1, 'L');
		}
		if(middle != NULL)
		{
			middle->printNode(level+1, 'M');
		}
		if(right != NULL)
		{
			right->printNode(level+1, 'R');
		}
	}
}